package queen

var (
	res [][]string = make([][]string, 0)
)

func solveNQueens(n int) [][]string {
	chessboard := make([][]byte, n)
	//初始化棋盘
	for i := 0; i < n; i++ {
		chessboard[i] = make([]byte, n)
		for j := 0; j < n; j++ {
			chessboard[i][j] = '.'
		}
	}
	backTack(chessboard, n, 0)
	return res
}

func backTack(chessboard [][]byte, n, row int) {
	if row == len(chessboard) {
		copyboard := make([]string, 0)
		for _, v := range chessboard {
			copyboard = append(copyboard, string(v))
		}
		res = append(res, copyboard)
		return
	}
	for col := 0; col < n; col++ {
		if !isValid(chessboard, n, row, col) {
			continue
		}
		chessboard[row][col] = 'Q'
		backTack(chessboard, n, row+1)
		chessboard[row][col] = '.'
	}
}

func isValid(chessboard [][]byte, n, row, col int) bool {
	for r := 0; r < n; r++ {
		if chessboard[r][col] == 'Q' {
			return false
		}
	}
	//判断右上方有没有Q
	i := row - 1
	j := col + 1
	for i >= 0 && j < n {
		if chessboard[i][j] == 'Q' {
			return false
		}
		i--
		j++
	}
	//判断左上方有没有Q
	i = row - 1
	j = col - 1
	for i >= 0 && j >= 0 {
		if chessboard[i][j] == 'Q' {
			return false
		}
		i--
		j--
	}
	//正确位置
	return true
}
